'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-04 11:23:50
'''
'''
我们这里举一个特别简单的例子，如图所示
            #####
        ->  # 1 #
    6 /     #####   \ 1
     /        ^       \
#####         |         ->#####
# 0 #         | 3         # 3 #
#####         |         ->#####
    \  2      |       / 5
      \     #####  /
       ->   # 2 #
            #####

假设$0,1,2,3$是四个公交站，他们都是单程的，每条边上边$\langle i, j\rangle$标出了从站$i$到站$j$所需时间。从图我们可以的大如下数据

$$
w = \begin{pmatrix}0&6&2&\infty\\
								\infty&0&\infty&1\\
								\infty&3&0&5\\
								\infty&\infty&\infty&0\end{pmatrix}\\
v = [0, 1, 2, 3]\\
dir = \{0:[1, 2], 2:[1, 2], 1:[3]\}
$$
式中$v$表示顶点，$dir$是邻接表，$w$是路径的权重。

'''
import sys
class Dijkstra:
    def __init__(self, v, w, dire):
        self.w = w #距离矩阵
        self.v = v #vertex集合
        self.dir = dire #邻接表
        self.visit = set([0]) #用于记录是否被访问过
        self.path = {} #用于记录每个被访问到的点的路径
        self.dis = [sys.maxsize]*len(v) #用于记录每个点到源点的距离
    
    def dijkstra(self):
        for i, v in enumerate(self.v):
            self.dis[i] = self.w[0][i]
            self.path[i] = [0, i]
        while len(self.visit)<len(self.v):
            tmp_ind = 0 #用于记录最小记录点
            tmp_dis = sys.maxsize #用于记录最小距离

            #寻找最小距离点
            for i, v in enumerate(self.dis):
                if v<tmp_dis and i not in self.visit:
                    tmp_ind = i
                    tmp_dis = v
            self.visit.add(tmp_ind)
            #用最小距离更新其邻接表内点的距离
            if tmp_ind in self.dir:
                for i, v in enumerate(self.dir[tmp_ind]):
                    if self.dis[v]> self.dis[tmp_ind]+self.w[tmp_ind][v]:
                        self.dis[v] = self.dis[tmp_ind]+self.w[tmp_ind][v]
                        self.path[v] = self.path[tmp_ind] + [v] #跟新路径
            

            

            

        


class Solution:
    def dijkstra(self, v, w, dire):
        self.dij = Dijkstra(v, w, dire)
        self.dij.dijkstra()

if __name__ == "__main__":
    v = [0,1,2,3]
    dire = {0:[1,2],2:[1,2],1:[3]}
    w = [[0, 6, 2, sys.maxsize], [sys.maxsize, 0, sys.maxsize, 1], [sys.maxsize, 3, 0, 5], [sys.maxsize, sys.maxsize, sys.maxsize, 0]]
    solution = Solution()
    solution.dijkstra(v, w, dire)
    print(solution.dij.dis[3], solution.dij.path[3])